package xyz.xiaotugou.algorithm;

/**
 * @author ysy
 * @version 1.0
 * @Title:  爬楼梯
 *              假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * @Note <b>ProjectName:</b> Pre-research
 * <br><b>PackageName:</b> xyz.xiaotugou.algorithm
 * <br><b>ClassName:</b> ClimbingStair
 * <br><b>Date:</b> 2022/1/11 22:21
 */
public class ClimbingStairs {

    /**
     * @Author ysy
     * @Description 找“重复子问题”：
     *                  - f(3) = f(2) + f(1) 【3级：最后一步要么2，要么1】
     *                  - f(4) = f(3) + f(2) 【4级：同样最后一步要么2，要么1】
     *                  - f(n) = f(n-1) + f(n-2)
     *              即为一个斐波拉契数列：
     *                      - 递归：时O(2^n)、空O(n)
     *                      - 记忆化递归：时O(n)、空O(n)
     *                      - 动态规划：时O(n)、空O(n)
     *                      - 裴波那契数列：时O(n)、空O(1)
     *                      - 数列通项公式：时O(log n)、空O(1)
     *                      - 矩阵快速幂：时O(log n)、空O(1)  【柯西-比内公式：矩阵乘法】
     *      https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
     *
     * @Date 2022/1/11 22:22
     * @Param 
     * @return int
     **/
    public static int climbingStairs(int stairs){
        // 台阶为1,只有1种、台阶为2,有两种
        if (stairs <= 2) {
            return stairs;
        }
        int n1=0, n2=0, count=1;
        for(int i=1; i<stairs; i++){
            n1=n2;
            n2=count;
            count=n1+n2;
        }
        return count    ;
    }

    public static void main(String[] args) {
        
    }
}
